The present application relates generally to an improved data processing apparatus and method and more specifically to mechanisms for performing transactional conflict resolution based on locality of threads executing conflicting transactions.
Transactional memory attempts to simplify concurrent or parallel programming by allowing a group of load and store instructions to execute in an atomic manner, i.e. it is guaranteed that either (1) all instructions of the transaction complete successfully or (2) no effects of the instructions of the transactions occur. With atomic transactions, the instructions of the transaction appear to occur all at once in a single instant between invocation and results being generated.
Hardware transactional memory systems may have modifications to the processors, caches, and bus protocols to support transactions or transaction blocks, i.e. groups of instructions that are to be executed atomically as one unit. Software transactional memory provides transactional memory semantics in a software runtime library with minimal hardware support.
As described in Bobba et al., “Performance Pathologies in Hardware Transactional Memory,” ISCA '07, Jun. 9-13, 2007, a programmer can invoke a transaction in a multi-threaded application and rely on the transactional memory system to make its execution appear atomic in a global serial order. Bobba et. al discusses conflict resolution policies in transactional memory systems, however, the concept of transactional memory was introduced by Herlihy and Moss “Transactional Memory: Architectural Support for Lock-Free Data Structures,” Proceedings of the 20th Annual International Symposium on Computer Architecture, pp. 289-300, May 1993.
Transactional memory systems seek high performance by speculatively executing transactions concurrently and only committing transactions that are non-conflicting. A conflict occurs when two or more concurrent transactions access the same piece of data, e.g. a word, block, object, etc., and at least one access is a write. Transactional memory systems may resolve some conflicts by stalling one or more transactions.
Transactional blocks are typically demarcated in a program with special transaction begin and end annotations. Transactional blocks may be uniquely identified by a static identifier, e.g., the address of the first instruction in the transactional block. Dynamically, multiple threads can concurrently enter a transaction block, although that transactional block will still share the same static identifier.